import java.util.*;

public class BinarySearch
{
    public static final int NOT_FOUND = -1;
    
    public static int sequentialSearch( Comparable [ ] a, Comparable x )
    {
	for (int i = 0; i < a.length; i++)
        {
	    if (a[i].compareTo( x ) == 0)
		return i;
        }
        return NOT_FOUND;     // NOT_FOUND = -1
    }
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( a[ mid ].compareTo( x ) < 0 )
                low = mid + 1;
            else if( a[ mid ].compareTo( x ) > 0 )
                high = mid - 1;
            else
                return mid;
        }
        return NOT_FOUND;     // NOT_FOUND = -1
    }

    public static void main( String [ ] args )
    {
      int SIZE = 8;
	for (SIZE = 100; SIZE < 100000; SIZE *= 2) {
        Comparable [ ] a = new Integer [ SIZE ];
        for( int i = 0; i < SIZE; i++ )
            a[ i ] = new Integer( i * 2 );

	long start, end;
	long elapsed1 = 0, elapsed2 = 0;
	/*
	*/
	start = System.currentTimeMillis();
        for( int i = 0; i < 100000; i++ )
	    sequentialSearch( a, new Integer( i ) );
	end = System.currentTimeMillis();
	elapsed1 = end - start;

	start = System.currentTimeMillis();
        for( int i = 0; i < 100000; i++ )
	    binarySearch( a, new Integer( i ) );
	end = System.currentTimeMillis();
	elapsed2 = end - start;

	System.out.println("size: " + SIZE + "\t" + "times: " + 
			   "\t" + elapsed1 + "\t" + elapsed2);

	}
    }
}